#include <stdio.h>


struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* partition(struct ListNode* pHead, int x) {
    struct  ListNode* head1, * tail1, * head2, * tail2;
    head1 = tail1 = head2 = tail2 = NULL;
    while (pHead)
    {
        if (pHead->val < x)
        {
            if (tail1 == NULL)
            {
                head1 = tail1 = pHead;
            }
            else
            {
                tail1->next = pHead;
                tail1 = pHead;
            }
            pHead = pHead->next;
        }
        else
        {
            if (tail2 == NULL)
            {
                head2 = tail2 = pHead;
            }
            else
            {
                tail2->next = pHead;
                tail2 = pHead;
            }
            pHead = pHead->next;
        }
    }
    if (head1 == NULL && head2 == NULL)
    {
        return NULL;
    }
    if (head1 == NULL && head2 != NULL)
    {
        return head2;
    }
    if (head1 != NULL && head2 == NULL)
    {
        tail1->next = NULL;
        return head1;
    }
    tail2->next = NULL;
    tail1->next = head2;
    return head1;
}
int main()
{
    struct ListNode* node1 = malloc(sizeof(struct ListNode));
    struct ListNode* node2 = malloc(sizeof(struct ListNode));
    struct ListNode* node3 = malloc(sizeof(struct ListNode));
    struct ListNode* node4 = malloc(sizeof(struct ListNode));
    struct ListNode* node5 = malloc(sizeof(struct ListNode));
    struct ListNode* node6 = malloc(sizeof(struct ListNode));
    node1->val = 3;
    node2->val = 1;
    node3->val = 3;
    node4->val = 5;
    node5->val = 6;
    node6->val = 3;

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node6;
    node6->next = NULL;

    node1 = partition(node1, 4);

    return 0;
}